Program Transformation and OLDT
a Personal Perspective

Taisuke Sato
Tokyo Institute of Technology
Japan

Editor: Enrico Pontelli

Warning: this  article is compiled from  my unreliable memory of the early days of program transformation in LP.

Long Long Ago

When  I  joined the  Electrotechnical  Laboratory (ETL),  a research institute under the ministry of trade and industry in Japan more than thirty years ago, symbolic AI was on the rise.  There was a strong group lead by Kazuhiro Fuchi, who initiated  and orchestrated  the Japanese  Fifth Generation Computer System  project (FGCS)  starting in 1982,  doing a variety  of AI  research from  image  understanding, speech recognition, natural language understanding, and so on.

What was  lucky to me  was that next year  Koichi Furukawa, who  became a  deputy director  of FGCS,  brought Marseille Prolog  into ETL  after a  visit to  the  Stanford Research Institute.   I could  have  a chance  of directly  touching Prolog.  Programs  looked mysterious (predicate  names were French!)  and  the interpreter written in  FORTRAN ran very slowly but this new  language seemed to promise an exciting future for me.

So  I gradually  shifted  from Lisp  that  was the  defacto standard AI language those days  to Prolog that was born in Europe a  couple years ago.   In the mean time  my research interest  switched  from  natural  language  processing  to Prolog.  There were so many fun things to do from theory to application. In  particular NAF  (negation-as-failure) attracted   me  because   firstly   it  was   theoretically mysterious  and  secondly I  simply  believed that  solving problems  with NAF  would  lead to  full first-order  logic programming, the unexplored realm of logic programming.  My problem  was  that I  didn't  have  a  concrete idea  about negation.

An Encounter with Partial Evaluation

In spring 1982, I went  to Kyoto.  My purpose was to attend the RIMS Symposium on  Software Science and Engineering and to give  a talk on intelligent backtracking  in Prolog.  In retrospect,  it  was  a  sheer coincidence  that  Yoshihiko Futamurna working  at Hitachi also  attended the symposium. He gave a talk on  partial evaluation and he was a tireless advocator of partial evaluation  though I did not  know anything about him.

He  explained so  called  "Futamura projection"  to us  and demonstrated   how  to   construct  a   compiler   from  an interpreter,  or more  ambitiously  a complier-compiler  by partial   evaluation. It was my first exposure  to unfold/fold   transformation  and   it   was  an   exciting experience: it  looked as if a  theory, partial evaluation, was going to achieve a real break through, the construction of mathematically  correct compiler. Although  he talked in the  context  of a  functional  programming, obviously  his
approach is applicable to Prolog. More to the point is that Prolog   has  unification  that   can  eliminate   all  the difficulties  in implementing  a partial  evaluator  by say
Lisp.

Being  galvanized by  the possibility  of  applying partial evaluation to logic programs, I returned to ETL in Tsukuba. I  tried  a  couple  of  transformation  examples  manually following  Futamura's   talk.The  first  one,  I  still remember,   was   to  derive   a   recursive  program   for initial(X,Z)  -  X  is  an  initial  list  of  Z  -  from
initial(X,Z):-append(X,Y,Z).   It was  done  easily.  Other examples (reverse, a string matcher, etc) were also easy. I was   quickly  convinced  of   the  power   of  unfold/fold transformation.

A  few days later,  encouraged by  this initial  success, I consulted Hisao Tamaki  on this emerging research subfield, unfold/fold  transformation in  logic programming.   He was staying at ETL as a  visiting scholar then and had a strong background  in  programming  language  and  algorithm.   He immediately  showed strong  interest and  it was  a natural consequence  that we began  working in  close collaboration beyond going for drink together.

Meaning Preserving Transformation

After  starting collaboration, we  knew that  logic program transformation was not no-man's land. Quite opposite. There was  already  a bunch  of  work.   Burstall and  Darlington published   their  famous   paper  on   functional  program transformation  in  1977.  Keith  Clark  and Sharon  Sickel applied their work to  logic program derivation in the same year.  Christopher Hogger  published a rather comprehensive paper on deductive derivation of logic programs in J.ACM in 1981.

We  noticed  however  that  their  framework  is  axiomatic deduction,  and  hence  while  every  computed  goal  by  a transformed  program  is   a  logical  consequence  of  the (if-and-only-if   completion  of)  original   program,  the converse  does not hold  in general.   In other  words, the equivalence  of transformed  programs in  the sense  of the least model semantics was not established yet.

Next  year, 1983, was  a busy  year.  While  publishing two papers on LP, one in  New Generation Computing 1(1) and the other at ICALP  in Barcelona, we continued to  try to prove equivalence  among  transformed  programs.  The  point  was clear: if p(X):- q(X) is immediately folded by p(X):-q(X), we get  p(X):-p(X), which must  be avoided. We  needed some condition that prevents this folding.

Tamaki  eventually hit the  necessary idea.   He introduced "rank" of a ground atom A based on the size of the smallest proof  tree of  A and  applied it  to determine  a foldable condition and thus completed  an equivalence proof.  In the end he  submitted a paper  on the equivalence proof  to the 2nd  ICLP in  Uppsala and  I submitted  a paper  on program synthesis using unfold/fold  transformation and negation to the 1st FGCS conference in Tokyo.

Append Optimizer

The mechanism of  unfold/fold transformation is general but real problems  are specific. To fill the  gap is equivalent to applying it to  a concrete problem. After publishing the unfold/fold paper, we looked for the next target.

Tamaki  again hit  a smart  idea, "Append  Optimizer".  The story goes  like this.   First we allow  a user to  write a logic program  freely using append/3.   But append/3 incurs redundancy (copy).  So we remove it by the Append Optimizer which automatically  introduces new data  structure similar to difference list to eliminate data copy by append/3.

It  has  turned  out  however  that  the  Append  Optimizer requires the dependency analysis of variables in a program. Worse  yet an  analyzer for  this purpose  often  goes into infinite  call as  it traces  the execution  of  the source program without  any input (goals  are completely general). Now the problem is to stop this infinite call.  The idea of tabling  came out  this  moment.  Indeed  necessity is  the mother of invention: tabling can stop infinite call.

Putting  aside  the Append  Optimizer,  he concentrated  on formalizing  tabling  in  logic  programming.   He  finally proved the  completeness of OLDT (OLD  with Tabulation) and presented it at the 3rd  ICLP in London in summer 1986 when I stayed at Imperial  College as a visiting researcher from ETL.

Looking Back

Regrettably the Append  Optimizer project was never resumed after  its   suspension.  I  do  not   remember  the  exact reason. Probably  because I was more  involved in extending unfold/fold transformation  to non-definite clauses  and he interest turned to concurrency.

Our  collaboration continued until  1989 when  we published two papers on logic  program synthesis.  Later Hisao Tamaki left  LP and  moved to  Toronto  to study  algorithm and  I slowly began  moving toward non-deductive  approaches in AI such as GA  and machine learning.

Looking back,  even had  we not proposed,  probably someone would   have  introduced  unfold/fold   transformation  and tabling to LP  anyway, but we are happy  that we could help their introduction to LP, which is all I can say now.